#include <unordered_map>
#include <vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
private:
    TreeNode* build(int pre_root, int left, int right, vector<int>& preorder, vector<int>& inorder, unordered_map<int, int>& inorder_map) {
        if (left > right) {
            return nullptr;
        }
        TreeNode* head = new TreeNode(preorder[pre_root]);
        int inorder_index = inorder_map[preorder[pre_root]];
        head->left = build(pre_root + 1, left, inorder_index - 1, preorder, inorder, inorder_map);
        head->right = build(pre_root + inorder_index - left + 1, inorder_index + 1, right, preorder, inorder, inorder_map);
        return head;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty()) {
            return nullptr;
        }
        unordered_map<int, int> inorder_map;
        for (int i = 0; i < inorder.size(); i++) {
            inorder_map[inorder[i]] = i;
        }
        return build(0, 0, preorder.size() - 1, preorder, inorder, inorder_map);
    }
};